home *** CD-ROM | disk | FTP | other *** search
/ Developer CD Series 1997 February: Technology Seed / Mac Tech Seed Feb '97.toast / OpenDoc 1.2b2c1 / OpenDoc / OpenDoc Utilities / Interfaces / StrHshTb.h < prev    next >
Encoding:
C/C++ Source or Header  |  1997-01-01  |  6.7 KB  |  217 lines  |  [TEXT/MPS ]
  1. /*
  2.     File:        StrHshTb.h
  3.  
  4.     Contains:    Interface to StringHashTable class.
  5.  
  6.     Owned by:    Reggie Adkins
  7.  
  8.     Copyright:    © 1993 - 1996 by Apple Computer, Inc., all rights reserved.
  9.  
  10.     Change History (most recent first):
  11.  
  12.          <3>     5/24/96    jpa        Fixed header
  13.          <2>     5/24/96    jpa        1339104: Speed optimizations (mostly for
  14.                                     EditorSetup)
  15.  
  16.     To Do:
  17. */
  18.  
  19. #ifndef _STRHSHTB_
  20. #define _STRHSHTB_
  21.  
  22. #ifndef _ODTYPES_
  23. #include "ODTypes.h"
  24. #endif
  25.  
  26. #ifndef _PLFMDEF_
  27. #include "PlfmDef.h"
  28. #endif
  29.  
  30. #ifndef _ODMEMORY_
  31. #include "ODMemory.h"
  32. #endif
  33.  
  34. #ifndef __STDIO__
  35. #include <stdio.h>
  36. #endif
  37.  
  38. //==============================================================================
  39. // Theory of Operation
  40. //==============================================================================
  41.  
  42. /*
  43.     A simple hash table for keys of variable length. Value is 8 bytes. First
  44.     four bytes are a pointer to the storage for the value, the next four bytes
  45.     are the length of that storage. The caller must allocate the storage.
  46.     Implemented with chaining. Keys are bytes streams. Embedded NULLs are
  47.     allowed. However, keys of zero length are not allowed.
  48. */
  49.  
  50. //==============================================================================
  51. // Scalar Types
  52. //==============================================================================
  53.  
  54. typedef ODULong (*StringHashTableFunc)(ODUByte* string,
  55.                                             ODULong stringLength,
  56.                                             ODULong& hashValueLowerBounds,
  57.                                             ODULong& hashValueUpperBounds);
  58.  
  59.     // this is the hash function prototype.
  60.  
  61. //==============================================================================
  62. // Classes defined in this interface
  63. //==============================================================================
  64.  
  65. class    StringHashTable;
  66. class    StringHashTableIterator;
  67.  
  68. //==============================================================================
  69. // Classes used by this interface
  70. //==============================================================================
  71.  
  72. class    LinkedNodesIterator;
  73. struct    HashEntryRec;
  74. struct    EntryNode;
  75.  
  76. //==============================================================================
  77. // StringHashTable
  78. //==============================================================================
  79.  
  80. class StringHashTable
  81. {
  82.     
  83.     friend class LinkedNodesIterator;
  84.     friend class StringHashTableIterator;
  85.  
  86.   public:
  87.  
  88.     StringHashTable(ODULong numEntries);
  89.         // numEntries should be the expected number of table entries. The table
  90.         //    will not grow or shrink. If zero is passed, the table is initialized
  91.         //    with 1 entry. (not very interesting).
  92.  
  93.     void Initialize(ODMemoryHeapID heapID);
  94.         // kODErrOutOfMemory will be thrown if the table could not be created.
  95.  
  96.     virtual ~StringHashTable();
  97.  
  98.  
  99.     void            Insert(ODUByte* string, ODULong stringLength,
  100.                                         ODPtr value, ODULong valueLength);
  101.         // If this key already exists, that value is replaced by the new value.
  102.         //     kODErrOutOfMemory will be thrown if the entry could not be inserted.
  103.         //    kODErrInvalidKey will be thrown if stringLength is zero.
  104.         //    The key is copied into the table, the value is not.
  105.         //    If an exception is 
  106.  
  107.     void            Remove(ODUByte* string, ODULong stringLength);
  108.         // No exception is thrown if the key does not exist.
  109.         //    kODErrInvalidKey will be thrown if stringLength is zero.
  110.  
  111.     ODBoolean         Find(ODUByte* string, ODULong stringLength,
  112.                                         ODPtr* value, ODULong* valueLength);    
  113.         // kODTrue is returned if the value is found, kODFalse otherwise.
  114.         //    If the entry is not found. *value and *valueLength are not
  115.         //    guaranteed to contain any useful information.
  116.         //    kODErrInvalidKey will be thrown if stringLength is zero.
  117.  
  118.     ODBoolean         Exists(ODUByte* string, ODULong stringLength);    
  119.         // kODTrue is returned if the value is found, kODFalse otherwise.
  120.         //    kODErrInvalidKey will be thrown if stringLength is zero.
  121.  
  122.     ODULong         GetNumEntries()        {return fNumEntries;}
  123.         // Return the number of entries.
  124.  
  125.     void        PrintTable(FILE* outfile);
  126.     void        PrintDistribution(FILE* outfile);
  127.     
  128.         // for debugging / testing
  129.  
  130.     StringHashTableFunc    GetHashFunc()    {return fHashFunc;}
  131.     void                SetHashFunc(StringHashTableFunc func)
  132.                                         {fHashFunc = func;}
  133.  
  134.         // get and set the hash function.
  135.  
  136.   protected:
  137.       ODMemoryHeapID         fHeapID;
  138.  
  139.     HashEntryRec*    fTable; // pointer to start of table,
  140.                             //    fNumSlots * sizeof(HashEntry) long. Initialized to
  141.                             //    all zeroes.
  142.  
  143.     ODULong        fNumSlots; // Number of slots in the table, not number of
  144.                                 //    entries.
  145.  
  146.     ODULong        fNumEntries;    // Actual number of entries.
  147.  
  148.     StringHashTableFunc    fHashFunc;
  149.     
  150.     HashEntryRec*    GetTable()            {return fTable;}
  151.     ODULong            GetNumSlots()        {return fNumSlots;}
  152.  
  153.     static ODULong        StdHash(ODUByte* string, ODULong stringLength,
  154.                                             ODULong& hashValueLowerBounds,
  155.                                             ODULong& hashValueUpperBounds);
  156.  
  157.     ODULong    MapToTableIndex(ODULong hash,
  158.                                             ODULong hashValueLowerBounds,
  159.                                             ODULong hashValueUpperBounds);
  160.  
  161.     ODULong    HashAndMap(ODUByte* string, ODULong stringLength);
  162.     void        InsertAtIndex(ODULong index, ODUByte* string,
  163.                                                 ODULong stringLength,
  164.                                                 ODPtr value,
  165.                                                 ODULong valueLength);
  166.     void        RemoveAtIndex(ODULong index, ODUByte* string,
  167.                                                 ODULong stringLength);
  168.     EntryNode*            MakeNewNode(ODUByte* string, ODULong stringLength,
  169.                                         ODPtr value, ODULong valueLength);
  170.     ODUByte*            MakeStringFromBytes(ODUByte* string,
  171.                                                     ODULong stringLength);
  172. };
  173.  
  174. //==============================================================================
  175. // StringHashTableIterator
  176. //
  177. //    This iterator is only meant to be used in the the context of a for loop,
  178. //    e.g.:
  179. //
  180. //    StringHashTableIterator iter;
  181. //    for (iter.First(string, len, value, valueLen);
  182. //            iter.IsNotComplete();
  183. //            iter.Next(string, len, value, valueLen))
  184. //    {
  185. //        ...
  186. //    }
  187. //
  188. //==============================================================================
  189.  
  190. class StringHashTableIterator
  191. {
  192.   public:
  193.     StringHashTableIterator(StringHashTable* tb);
  194.     ~StringHashTableIterator()        { }
  195.     void        First(ODUByte** string, ODULong* len, ODPtr* value,
  196.                           ODULong* valueLen);
  197.         // A pointer to the private copy of the string is returned. The user
  198.         //    must copy the storage if he or she desires to change it.
  199.         //    If there are no entries in the table, *string will be set to
  200.         //    kODNULL and *len set to 0.
  201.     void        Next(ODUByte** string, ODULong* len, ODPtr* value,
  202.                         ODULong* valueLen);
  203.         // A pointer to the private copy of the string is returned. The user
  204.         //    must copy the storage if he or she desires to change it.
  205.         //    If there are no more entries in the table, *string will be set to
  206.         //    kODNULL and *len set to 0.
  207.     ODBoolean    IsNotComplete()        {return !fDone;}
  208.   private:
  209.     ODBoolean    GetNext(ODUByte** string, ODULong* len,
  210.                         ODPtr* value, ODULong* valueLen);
  211.     StringHashTable*    fTable;
  212.     ODULong            fTableIndex;
  213.     EntryNode*            fCurNode;
  214.     ODBoolean            fDone;
  215. };
  216.  
  217. #endif // _STRHSHTB_